/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/* 
 * Copyright (c) 2009 City University of Hong Kong
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License m_version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * 
 * Author: Wilson Thong (wilsonwk@ee.cityu.edu.hk) 
 */

#include <iostream>
#include <fstream>
#include <string>
#include <cassert>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <set>
#include <functional>
#include <iterator>
#include <utility>

#include <math.h>

#include "ns3/packet-sink.h"
#include "ns3/test.h"
#include "ns3/pointer.h"
#include "ns3/enum.h"
#include "ns3/command-line.h"
#include "ns3/config.h"
#include "ns3/boolean.h"
#include "ns3/node-list.h"
#include "ns3/channel-list.h"
#include "ns3/udp-client-server-helper.h"
#include "ns3/uinteger.h"
#include "ns3/packet-sink-helper.h"
#include "ns3/point-to-point-net-device.h"
#include "ns3/point-to-point-channel.h"
#include "ns3/application-container.h"
#include "ns3/inet-socket-address.h"
#include "ns3/log.h"
#include "ns3/queue.h"
#include "ns3/ipv4-global-routing-helper.h"
#include "ns3/simulator.h"
#include "ns3/flow-monitor.h"
#include "complex-behavior-tools.h"

namespace ns3 {
namespace eecityu {

using namespace std;

NS_LOG_COMPONENT_DEFINE ("ComplexBehaviorTools");

Ptr<Node>
GetRemoteNode (Ptr<Node> local, uint32_t devId)
{
  // to be pointing the remote node
  Ptr<Node> remote = 0;
  // get the two nodes on the channel attached to the net device
  uint32_t degree = local->GetNDevices ();
  NS_ASSERT_MSG (devId <= degree, "GetRemoteNode(): The devId is out of the range");
  Ptr<PointToPointNetDevice> localDev = DynamicCast<PointToPointNetDevice> (local->GetDevice (devId));
  // set the flag to false if the net device is not a PointToPointNetDevice
  bool isP2p = true;
  if (!localDev) {
    isP2p = false;
    NS_LOG_DEBUG ("The net device (devId = " << devId << ") is not a PointToPointNetDevice");
  }
  if (isP2p) {
    Ptr<PointToPointChannel> channel = DynamicCast<PointToPointChannel> (localDev->GetChannel ());
    NS_ASSERT_MSG (channel, "GetRemoteNode(): The channel is not a PointToPointChannel");
    Ptr<PointToPointNetDevice> dev0 = channel->GetPointToPointDevice (0);
    Ptr<PointToPointNetDevice> dev1 = channel->GetPointToPointDevice (1);
    Ptr<Node> node0 = dev0->GetNode ();
    Ptr<Node> node1 = dev1->GetNode ();
    // return one of the two nodes which is not the local one
    if (node0->GetId () != local->GetId ())
      remote = node0;
    else if (node1->GetId () != local->GetId ())
      remote = node1;
    else
      NS_ASSERT_MSG (false, "GetRemoteNode(): Program reaches an unexpected point");
  }
  return remote;
}

/**
 * \internal 
 *
 * \return True if n1's ID is less then n2's ID
 */
bool 
NodeLess (Ptr<Node> n1, Ptr<Node> n2)
{
  return n1->GetId () < n2->GetId ();
}

/**
 * \internal 
 *
 * \return True if n1's ID is equal to n2's ID
 */
bool 
NodeEqual (Ptr<Node> n1, Ptr<Node> n2)
{
  return (!NodeLess (n1, n2)) && (!NodeLess (n2, n1));
}

typedef deque <Ptr<Node> > WaitQueue_t;
ostream& 
operator<< (ostream& os, const WaitQueue_t& v)
{
  for (uint32_t i=0; i<v.size (); i++) {
    if (i>0) os << ", ";
    os << v.at (i)->GetId ();
  }
  return os;
}

ostream&
operator<< (ostream& os, const NodeContainer& c)
{
  for (uint32_t i=0; i<c.GetN (); i++) {
    if (i>0) os << ", ";
    os << c.Get (i)->GetId ();
  }
  return os;
}

NodeContainer
GetNeighborsAtHop (Ptr<Node> root, uint32_t hop)
{
  NS_ASSERT_MSG (root > 0, "GetNeighborsAtHop(): 'root' cannot be a NULL pointer");
  NS_LOG_FUNCTION (root->GetId () << hop);
  NS_ASSERT_MSG (hop >= 0, "GetNeighborsAtHop(): hop cannot be a negative number");

  // nodeDist contains all nodes discovered and their distance from the root node
  typedef map<Ptr<Node>, uint32_t, bool(* )(Ptr<Node>, Ptr<Node>)> NodeDistMap_t;
  NodeDistMap_t nodeDist (NodeLess);
  // initialize the root node distance to 0
  nodeDist[root] = 0;
  // waitQueue contains all nodes waiting for their direct neighbors to be searched
  WaitQueue_t waitQueue;
  waitQueue.push_back (root);

  // will contain all the neighbor at 'hop' distance away from root node. this is the 
  // container returned to the caller
  NodeContainer hopNeighbors;
  // search for all direct neighbors of nodes contained in the 'waitQueue'
  while (!waitQueue.empty ()) {
    // pop a node from the back of the 'waitQueue'
    Ptr<Node> local = waitQueue.front ();
    waitQueue.pop_front ();
    uint32_t localDist = nodeDist.find (local)->second;
    if (localDist == hop) {
      // the 'local' node is found to have the 'hop' distance away from the root, thus
      // no further searching is needed from 'local' node
      hopNeighbors.Add (local);
      continue;
    }
    // chcek the distance of all direct neighbors of 'local'. if a neighbor node
    // has not yet a distance record in 'nodeDist', set it a new distance and 
    // push the node into the 'waitQueue'. otherwise, do nothing on the neighbor
    // node as it is already discovered
    uint32_t localNDev = local->GetNDevices ();
    for (uint32_t i=0; i<localNDev; i++) {
      Ptr<Node> neighbor = GetRemoteNode (local, i);
      // skip this i-th net device if 'GetRemoteNode' returns a null pointer.
      // this is the case if the net device is not a PointToPointNetDevice
      if (!neighbor) continue;        
      NodeDistMap_t::iterator iter = nodeDist.find (neighbor);
      if (iter == nodeDist.end ()) {
        // the neighbor node has not yet a distance record in the 'nodeDist'
        nodeDist[neighbor] = localDist + 1;
        waitQueue.push_back (neighbor);
      } // else, ignore this neighbor node
    }
  }
  return hopNeighbors;
}

pair<Ptr<Node>, Ptr<Node> >
GetTwoNodesAtRandom (uint32_t hopDistance)
{
  NS_ASSERT_MSG (hopDistance > 0, "Cannot randomly get two nodes with 0 hop distance inbetween");
  // the two nodes to be selected at random
  Ptr<Node> srcNode = 0;
  Ptr<Node> dstNode = 0;
  // select one node at random among all nodes
  uint32_t numNodes = NodeList::GetNNodes ();
  UniformVariable urand;
  uint32_t srcId = urand.GetInteger (0, numNodes-1);
  srcNode = NodeList::GetNode (srcId);
  // find out all nodes that are 'hopDistance' away from srcNode
  NodeContainer neighbors = GetNeighborsAtHop (srcNode, hopDistance);
  uint32_t numNeighbors = neighbors.GetN ();
  if (numNeighbors > 0) {
    uint32_t dstId = urand.GetInteger (0, numNeighbors-1);
    dstNode = neighbors.Get (dstId);
  }
  if (!dstNode) {    
    NS_LOG_DEBUG ("Node-" << srcNode->GetId () <<" does not have any nodes at " << hopDistance << " hops away");
    srcNode = 0;
    dstNode = 0;    
  }
  // return the two randomly selected nodes
  return make_pair (srcNode, dstNode);
}

struct EdgeAttr_t {
  uint32_t nodeId0; // node ID of one end of an edge
  uint32_t nodeId1; // node ID of the othe end of an edge
  double utility; // % of link's bandwidth utilization
  double bw; // link bandwidth
};

void
WriteGraph (string filename, Time duration, bool merging)
{
  // to contain attributes of all edges
  vector<EdgeAttr_t> allEdgeAttrVec;

  // go through each channel, calculate statistics and write them into the file
  ChannelList::Iterator iter = ChannelList::Begin ();
  ChannelList::Iterator iterEnd = ChannelList::End ();
  for (; iter != iterEnd; iter++) {
    // get all the necessary pointers to the ns3 objects at both ends of an edge
    Ptr<PointToPointChannel> channel = DynamicCast<PointToPointChannel> (*iter);
    Ptr<PointToPointNetDevice> dev0 = channel->GetPointToPointDevice (0);
    Ptr<PointToPointNetDevice> dev1 = channel->GetPointToPointDevice (1);
    Ptr<Node> node0 = dev0->GetNode ();
    Ptr<Node> node1 = dev1->GetNode ();
    PointerValue queue0Value, queue1Value;
    dev0->GetAttribute ("TxQueue", queue0Value);
    dev1->GetAttribute ("TxQueue", queue1Value);
    Ptr<Queue> queue0 = queue0Value.Get<Queue> ();
    Ptr<Queue> queue1 = queue1Value.Get<Queue> ();

    // get all the necessary information from these ns3 objects
    DataRateValue bw0Value, bw1Value;
    dev0->GetAttribute ("DataRate", bw0Value);
    dev1->GetAttribute ("DataRate", bw1Value);
    double bw0 = bw0Value.Get ().GetBitRate ();
    double bw1 = bw1Value.Get ().GetBitRate ();
    uint32_t queue0RxBits = queue0->GetTotalReceivedBytes () * 8;
    uint32_t queue1RxBits = queue1->GetTotalReceivedBytes () * 8;

    if (merging) {
      // calculate averaged statistics and mering two links into one
      EdgeAttr_t attr;
      attr.nodeId0 = node0->GetId ();
      attr.nodeId1 = node1->GetId ();
      attr.bw = (bw0 + bw1) / 2.0;
      attr.utility = (double) (queue0RxBits + queue1RxBits) / duration.GetSeconds () / (bw0 + bw1);
      // add the statistics into the container for later writing into a file
      allEdgeAttrVec.push_back (attr);
    } else {
      EdgeAttr_t attr0, attr1;
      // calculate averged statistics of one link
      attr0.nodeId0 = node0->GetId ();
      attr0.nodeId1 = node1->GetId ();
      attr0.bw = bw0;
      attr0.utility = (double) (queue0RxBits) / duration.GetSeconds () / bw0;
      // calculate averged statistics of the other link
      attr1.nodeId0 = node1->GetId ();
      attr1.nodeId1 = node0->GetId ();
      attr1.bw = bw1;
      attr1.utility = (double) (queue1RxBits) / duration.GetSeconds () / bw1;
      // add the statistics into the container for later writing into a file
      allEdgeAttrVec.push_back (attr0);
      allEdgeAttrVec.push_back (attr1);
    }
  }

  ofstream of (filename.c_str ());
  of << "Src\tDst\tBw(bps)\tUtility" << endl;
  for (vector<EdgeAttr_t>::const_iterator it = allEdgeAttrVec.begin (); it != allEdgeAttrVec.end (); it++){
    const EdgeAttr_t& attr = *it;
    of << attr.nodeId0 << '\t'
       << attr.nodeId1 << '\t'
       << attr.bw << '\t'
       << attr.utility << endl;
  }
  of.close ();
}

ApplicationContainer
InstallTrafficFlow (Ptr<Node> src, Ptr<Node> dst, DataRate dataRate, uint32_t numPkt, uint32_t pktSize)
{
  ApplicationContainer apps;

  Ptr<Node> srcNode = src;
  Ptr<Node> dstNode = dst;
  Ptr<Ipv4> dstIpv4 = dstNode->GetObject<Ipv4> ();
  Ipv4Address dstAddr = dstIpv4->GetAddress (1, 0).GetLocal ();
  // allocate an unused port on destination node
  uint16_t dstPort = 10001 + dstNode->GetNApplications ();
  // set the data rate for the Poisson traffic stream
  DataRate srcDataRate  = dataRate;
  // install a traffic source application
  UdpClientHelper client (dstAddr, dstPort);
  client.SetAttribute ("PacketSize", UintegerValue (pktSize));
  double packetRate = (double) srcDataRate.GetBitRate () / ((double) pktSize * 8.0);
  client.SetAttribute ("Interval", RandomVariableValue (ExponentialVariable (1.0/packetRate)));
  client.SetAttribute ("MaxPackets", UintegerValue (numPkt));    
  apps.Add (client.Install (srcNode));
  // install a traffic sink application
  PacketSinkHelper sink ("ns3::UdpSocketFactory", Address (InetSocketAddress (Ipv4Address::GetAny (), dstPort)));
  apps.Add (sink.Install (dstNode));
  
  NS_LOG_DEBUG ("Installed Poisson flow " << srcNode->GetId () << " -> " << dstNode->GetId ());

  return apps;
}

ApplicationContainer
InstallRandomTraffic (uint32_t numFlows, uint32_t flowDistance, DataRate flowRate, uint32_t pktSize)
{
  // install a Poisson traffic flow one by one
  for (uint32_t i=0; i<numFlows; i++) {
    pair<Ptr<Node>, Ptr<Node> > srcDst = GetTwoNodesAtRandom (flowDistance);
    Ptr<Node> srcNode = srcDst.first;
    Ptr<Node> dstNode = srcDst.second;
    InstallTrafficFlow (srcNode, dstNode, flowRate, pktSize);
  }
}

ApplicationContainer
InstallGridTraffic (PointToPointGridHelper grid, uint32_t nRows, uint32_t nCols, 
                    uint32_t flowLength, DataRate flowRate, uint32_t numPkt, uint32_t pktSize)
{
  ApplicationContainer apps;
  // go to each node of the grid, and install traffic flows
  for (uint32_t r=0; r<nRows; r++) {
    for (uint32_t c=0; c<nCols; c++) {
      // install northward (^) traffic flow
      if (r >= flowLength) {
        apps.Add (InstallTrafficFlow (grid.GetNode (r, c), grid.GetNode (r-flowLength, c), flowRate, numPkt, pktSize));
      }
      // install eastward (->) traffic flow
      if (c+flowLength < nCols) {
        apps.Add (InstallTrafficFlow (grid.GetNode (r, c), grid.GetNode (r, c+flowLength), flowRate, numPkt, pktSize));
      }
      // install southward (V) traffic flow
      if (r+flowLength < nRows) {
        apps.Add (InstallTrafficFlow (grid.GetNode (r, c), grid.GetNode (r+flowLength, c), flowRate, numPkt, pktSize));
      }
      // install westward (<-) traffic flow
      if (c >= flowLength) {
        apps.Add (InstallTrafficFlow (grid.GetNode (r, c), grid.GetNode (r, c-flowLength), flowRate, numPkt, pktSize));
      }
    }
  }
  return apps;
}

ApplicationContainer
InstallBackgroundTraffic (double linkUtil, uint32_t pktSize)
{
  NS_ASSERT_MSG (linkUtil >= 0.0, "InstallBackgroundTraffic(): link utilization cannot below 0.0 (whereas equal is allowed)");

  ChannelList::Iterator chIter = ChannelList::Begin ();
  ChannelList::Iterator chEnd = ChannelList::End ();
  ApplicationContainer apps;

  // go through all channel and add a Poisson traffic in each direction  
  for (; chIter != chEnd; chIter++) {
    // get the two net devices on the channel and allocate a Poisson traffic for each net device
    Ptr<PointToPointChannel> channel = DynamicCast<PointToPointChannel> (*chIter);
    Ptr<PointToPointNetDevice> devs[2];
    devs[0] = channel->GetPointToPointDevice (0);
    devs[1] = channel->GetPointToPointDevice (1);
    // go through both direction of the channel and install a Poisson flow
    for (int i=0; i<2; i++) {
      // obtain the srouce node and destination node IP addresses
      //
      // <(i % 2), (i+1 %2)> are either <0, 1> or <1, 0>, so 
      // the two net devices are selected in turn to be a source 
      // net device and a destination net device
      Ptr<PointToPointNetDevice> srcDev = devs[i % 2];
      Ptr<PointToPointNetDevice> dstDev = devs[(i+1) % 2];
      Ptr<Node> srcNode = srcDev->GetNode ();
      Ptr<Node> dstNode = dstDev->GetNode ();
      // obtain net device's bandwidth
      DataRateValue srcLineSpeedValue;
      srcDev->GetAttribute ("DataRate", srcLineSpeedValue);
      DataRate srcLineSpeed (srcLineSpeedValue.Get ().GetBitRate ());
      // calculate the data rate from the given link utilization
      DataRate srcDataRate ((double) srcLineSpeed.GetBitRate () * linkUtil);
      // install a Poisson traffic flow between the source and the destination node
      apps.Add (InstallTrafficFlow (srcNode, dstNode, srcDataRate, pktSize));      
    }
  }

  return apps;
}

void CloseGridEdge (
  uint32_t nRows, 
  uint32_t nCols, 
  PointToPointHelper p2p,
  PointToPointGridHelper grid)
{
  // the index to the last row
  uint32_t lastRow = nRows-1;
  // the index to the last column
  uint32_t lastCol = nCols-1;

  // add one more link for each row to close the two vertical 
  // edges of the grid topology
  for (uint32_t r=0; r<nRows; r++) {
    // get the two nodes on the two vertical edges
    NodeContainer nodes;
    nodes.Add (grid.GetNode (r, 0));
    nodes.Add (grid.GetNode (r, lastCol));
    // install one additional horizontal link
    p2p.Install (nodes);
  }
  // add one morelink for each column to close the two horizontal 
  // edges of the grid topology
  for (uint32_t c=0; c<nCols; c++) {
    // get the two nodes on the two vertical edges
    NodeContainer nodes;
    nodes.Add (grid.GetNode (0, c));
    nodes.Add (grid.GetNode (lastRow, c));
    // install one additional horizontal link
    p2p.Install (nodes);
  }
}

void 
NotifyProgressEvery (Time interval)
{
  // get the current time and stop time
  Time current = Simulator::Now ();
  // notify users
  cout.precision (2);
  cout << fixed << "current time = " << current.GetSeconds () << "sec" << endl << flush;  
  if (!Simulator::IsFinished ())
    Simulator::Schedule (interval, NotifyProgressEvery, interval);
}

/**
 * \brief Count the total number of deflections done by Ipv4DeflectionRouting
 *
 * \param counter The counter calculator for storing the counts
 * \param header The IPv4 header of the packet being deflected
 * \param p The packet being deflected
 * \param prefer The preferred route for the packet before deflection
 * \param deflect The deflected route for the packet after deflection
 */
void 
CountTotalDeflection (Ptr<CounterCalculator<> > counter, const Ipv4Header& header, Ptr<const Packet> p, Ptr<Ipv4Route> prefer, Ptr<Ipv4Route> deflect)
{
  NS_LOG_FUNCTION (counter << header << p << prefer << deflect);
  counter->Update ();
}

void
TraceConnectForCountDeflection (Ptr<CounterCalculator<> > counter, PointToPointGridHelper grid, uint32_t rows, uint32_t cols)
{
  for (uint32_t r=0; r<rows; r++) {
    for (uint32_t c=0; c<cols; c++) {
      Ptr<Node> n = grid.GetNode (r, c);
      uint32_t nId = n->GetId ();
      stringstream oss;
      oss << "/Names/Ipv4DeflectionRouting" << nId << "/DeflectionTrace";
      Config::ConnectWithoutContext (oss.str (), MakeBoundCallback (&CountTotalDeflection, counter));
    }
  }
}

void
CountTotalPktHopping (Ptr<MinMaxAvgTotalCalculator<> > counter, 
                        FlowId flowId, FlowPacketId packetId, 
                        const FlowMonitor::FlowStats* stats, const FlowMonitor::TrackedPacket* tracked)
{
  NS_ASSERT (tracked != 0);
  counter->Update (tracked->timesForwarded);
}

void
TraceConnectForCountTxPacketTotalForwarding (Ptr<MinMaxAvgTotalCalculator<> > counter, Ptr<FlowMonitor> flowmon)
{
  flowmon->TraceConnectWithoutContext ("ReportLastRx", MakeBoundCallback (CountTotalPktHopping, counter));
  flowmon->TraceConnectWithoutContext ("ReportDrop", MakeBoundCallback (CountTotalPktHopping, counter));
}

void
TraceConnectForCountRxPacketTotalForwarding (Ptr<MinMaxAvgTotalCalculator<> > counter, Ptr<FlowMonitor> flowmon)
{
  flowmon->TraceConnectWithoutContext ("ReportLastRx", MakeBoundCallback (CountTotalPktHopping, counter));
}

void
CountTotalPacketTimelife (Ptr<TimeMinMaxAvgTotalCalculator> counter, 
                          FlowId flowId, FlowPacketId packetId, 
                          const FlowMonitor::FlowStats* stats, const FlowMonitor::TrackedPacket* tracked)
{
  Time lifetime = tracked->lastSeenTime - tracked->firstSeenTime;
  counter->Update (lifetime);
}

void
TraceConnectForCountTotalPacketTimelife (Ptr<TimeMinMaxAvgTotalCalculator> counter, Ptr<FlowMonitor> flowmon)
{
  flowmon->TraceConnectWithoutContext ("ReportLastRx", MakeBoundCallback (CountTotalPacketTimelife, counter));
  flowmon->TraceConnectWithoutContext ("ReportDrop", MakeBoundCallback (CountTotalPacketTimelife, counter));
}

void
TraceConnectForCountTotalBytesAcrossLinks (Ptr<PacketSizeMinMaxAvgTotalCalculator> counter, 
                                           PointToPointGridHelper grid, uint32_t rows, uint32_t cols) 
{
  // go to each node, and connect the counter to each of the node's net devices
  for (uint32_t r=0; r<rows; r++) {
    for (uint32_t c=0; c<cols; c++) {
      Ptr<Node> n = grid.GetNode (r, c);
      uint32_t id = n->GetId ();

      std::ostringstream oss;
      oss << "/NodeList/" << id << "/DeviceList/*/$ns3::PointToPointNetDevice/PhyRxEnd";
      Config::Connect (oss.str (), MakeCallback (&PacketSizeMinMaxAvgTotalCalculator::PacketUpdate, counter));
    }
  }
}

void
CountEventsOverTime (Ptr<HistogramCalculator> hist, 
                     FlowId flowId, FlowPacketId packetId, 
                     const FlowMonitor::FlowStats* stats, const FlowMonitor::TrackedPacket* tracked)
{
  hist->AddValue (Simulator::Now ().GetSeconds ());
}


void
TraceConnectCountPacketSentOverTime (Ptr<HistogramCalculator> hist, Ptr<FlowMonitor> flowmon)
{
  flowmon->TraceConnectWithoutContext ("ReportFirstTx", MakeBoundCallback (CountEventsOverTime, hist));
}

void
TraceConnectCountPacketReceivedOverTime (Ptr<HistogramCalculator> hist, Ptr<FlowMonitor> flowmon)
{
  flowmon->TraceConnectWithoutContext ("ReportLastRx", MakeBoundCallback (CountEventsOverTime, hist));
}

void
TraceConnectCountPacketDroppedOverTime (Ptr<HistogramCalculator> hist, Ptr<FlowMonitor> flowmon)
{
  flowmon->TraceConnectWithoutContext ("ReportDrop", MakeBoundCallback (CountEventsOverTime, hist));
}

void
CountNumActivePacketOverTime (Histogram* out, Histogram* tx, Histogram* rx, Histogram* drop)
{
  // counter for the accumuated number of active packets
  int32_t count = 0;
  // if this flag is still true at the end of this while loop, break this loop
  bool finish = false;
  for (uint32_t i=0; !finish; i++)
    {
      finish = true;
      // accumulate the number of active packets into the 'count'
      if (tx->GetNBins () > i) 
        {
          count += tx->GetBinCount (i);
          finish = false;
          NS_LOG_DEBUG ("At time = " << tx->GetBinStart (i) << ", tx = " << tx->GetBinCount (i));
        }
      if (rx->GetNBins () > i) 
        {
          count -= rx->GetBinCount (i);
          finish = false;
          NS_LOG_DEBUG ("At time = " << rx->GetBinStart (i) << ", rx = " << rx->GetBinCount (i));
        }
      if (drop->GetNBins () > i) 
        {
          count -= drop->GetBinCount (i);
          finish = false;
          NS_LOG_DEBUG ("At time = " << drop->GetBinStart (i) << ", drop = " << drop->GetBinCount (i));
        }
      // give a warning message if 'count' becomes negative
      if (count < 0)
        {
          NS_LOG_WARN ("Number of active packets in the network is negative at time " << tx->GetBinStart (i) << "-" << tx->GetBinEnd (i));
        }
      else 
        {
          // if 'count' value is positive, update the 'out' histogram
          // get the center value of the bin
          double currentTime = 0.5 * (tx->GetBinStart (i) + tx->GetBinEnd (i));
          // add the current time value into the output histogram for the 'count' number of times
          for (uint32_t j=0; j<count; j++)         
            {
              out->AddValue (currentTime);
              NS_LOG_DEBUG ("Add to out histogram the value = " << currentTime);
            }
        }
      NS_LOG_DEBUG ("At time = " << tx->GetBinStart (i) << ", active = " << count);
    }
}

double
GetTimeInterval (uint32_t numPackets, uint32_t packetSize, DataRate dataRate, uint32_t numIntervals)
{
  double interval = dataRate.CalculateTxTime (numPackets * packetSize);
  // divide the entire simulation period to at least 100 intervals
  interval /= numIntervals;
  NS_LOG_DEBUG ("interval (before adjust) = " << interval);
  // align the interval so that 0.135 becomes 0.1, 1352.9 becomes 1000.0, etc.
  NS_LOG_DEBUG ("exp = " << exp);
  double exp = floor (log10 (interval));
  NS_LOG_DEBUG ("exp = floor (log10 (interval)); exp = " << exp);
  interval = pow (10.0, exp);
  NS_LOG_DEBUG ("interval (after adjust) = " << interval);

  return interval;  
}

HistogramCalculator::HistogramCalculator ()
: Histogram (), DataCalculator ()
{}

HistogramCalculator::HistogramCalculator (double binWidth)
: Histogram (binWidth), DataCalculator ()
{}


void 
HistogramCalculator::Output(DataOutputCallback &callback) const
{
  uint32_t numBins = GetNBins ();
  for (uint32_t i=0; i<numBins; i++) {
    double binStart = const_cast<HistogramCalculator*>(this)->GetBinStart (i);
    uint32_t count = const_cast<HistogramCalculator*>(this)->GetBinCount (i);
    stringstream contextOss;
    if (m_context.size () == 0)
      contextOss << binStart;
    else
      contextOss << m_context << "," << binStart;
    callback.OutputSingleton (contextOss.str (), m_key, count);
  }
}

void 
HistogramCalculator::AddValue (double value)
{
  // implement the enable/disable feature provided by DataCalculator class
  if (m_enabled) 
    {
      Histogram::AddValue (value);
    }
}


/*******************************************************************/
/* Defining test cases and test suite                              */
/*******************************************************************/

uint32_t 
GetNodeId (Ptr<Node> n)
{
  return n->GetId ();
}

bool 
NodeIdEqual (Ptr<Node> n, uint32_t id)
{
  return n->GetId () == id;
}

template <size_t _Size> bool 
operator== (NodeContainer nodes, uint32_t (&ids)[_Size])
{
  bool isEqual = true;
  for (uint32_t i=0; i<nodes.GetN () && isEqual; i++) {
    uint32_t* iter = find (ids, ids+_Size, nodes.Get (i)->GetId ());
    if (iter == ids+_Size)
      isEqual = false;
  }
  return isEqual;
}

template <size_t _Size> ostream&
operator<< (ostream& os, uint32_t (&ids)[_Size])
{
  for (size_t i=0; i<_Size; i++) {
    if (i>0) os << ", ";
    os << ids[i];
  }
  return os;
}

class CountNumActivePacketOverTimeTestCase : public TestCase
{
public:
  CountNumActivePacketOverTimeTestCase () : TestCase ("Test the function for counting number of active packets in a network") {}
  virtual bool DoRun (void) {

    double interval = 0.1;
    // count number of active packets
    Histogram active (interval);
    // count number of packet sent
    Histogram tx (interval);
    // count number of packet received
    Histogram rx (interval);
    // count number of packet dropped
    Histogram drop (interval);

    // Following list out a test case for sending, receiving, and dropping packets
    // time   tx   rx   drop   active
    // 0.05   o                1
    // 0.15   o                2
    // 0.25   o    o           2
    // 0.35   o    o           2
    // 0.45             o      1
    // 0.55        o           0
    // 0.65   o                1
    // 0.75   o                2
    // 0.85        o    o      0
    tx.AddValue (0.05);
    tx.AddValue (0.15);
    tx.AddValue (0.25);
    tx.AddValue (0.35);
    tx.AddValue (0.65);
    tx.AddValue (0.75);

    rx.AddValue (0.25);
    rx.AddValue (0.35);
    rx.AddValue (0.55);
    rx.AddValue (0.85);

    drop.AddValue (0.45);
    drop.AddValue (0.85);

    // test the function correctness
    CountNumActivePacketOverTime (&active, &tx, &rx, &drop);
    NS_TEST_ASSERT_MSG_EQ (active.GetNBins (), 8, "Incorrect number of bins for the active packets histogram");
    NS_TEST_EXPECT_MSG_EQ (active.GetBinCount (0), 1, "Incorrect active packets counting");
    NS_TEST_EXPECT_MSG_EQ (active.GetBinCount (1), 2, "Incorrect active packets counting");
    NS_TEST_EXPECT_MSG_EQ (active.GetBinCount (2), 2, "Incorrect active packets counting");
    NS_TEST_EXPECT_MSG_EQ (active.GetBinCount (3), 2, "Incorrect active packets counting");
    NS_TEST_EXPECT_MSG_EQ (active.GetBinCount (4), 1, "Incorrect active packets counting");
    NS_TEST_EXPECT_MSG_EQ (active.GetBinCount (5), 0, "Incorrect active packets counting");
    NS_TEST_EXPECT_MSG_EQ (active.GetBinCount (6), 1, "Incorrect active packets counting");
    NS_TEST_EXPECT_MSG_EQ (active.GetBinCount (7), 2, "Incorrect active packets counting");

    return false;
  }
};

class GetTimeIntervalTestCase : public TestCase
{
public:
  GetTimeIntervalTestCase () : TestCase ("Test dividing the entire simulation preiod into some intervals") {}
  virtual bool DoRun (void) {
    double interval1 = GetTimeInterval (1000, 1000, DataRate ("10MB/s"), 100);
    double interval2 = GetTimeInterval (1000, 1000, DataRate ("29MB/s"), 100);
    double interval3 = GetTimeInterval (1000, 1000, DataRate ("99.9MB/s"), 100);
    double interval4 = GetTimeInterval (1000, 1000, DataRate ("100MB/s"), 100);
    double interval5 = GetTimeInterval (1000, 1000, DataRate ("586MB/s"), 100);

    NS_TEST_EXPECT_MSG_EQ_TOL (interval1, 0.001, 1e-12, "Incrrect calculation of time interval");
    NS_TEST_EXPECT_MSG_EQ_TOL (interval2, 0.0001, 1e-12, "Incrrect calculation of time interval");
    NS_TEST_EXPECT_MSG_EQ_TOL (interval3, 0.0001, 1e-12, "Incrrect calculation of time interval");
    NS_TEST_EXPECT_MSG_EQ_TOL (interval4, 0.0001, 1e-12, "Incrrect calculation of time interval");
    NS_TEST_EXPECT_MSG_EQ_TOL (interval5, 0.00001, 1e-12, "Incrrect calculation of time interval");   

    return false;
  };
};

class GetNeighborsAtHopTestCase : public TestCase
{
public:
  GetNeighborsAtHopTestCase () : TestCase ("Test getting the nodes some hops distance apart from a root") {}
  virtual bool DoRun (void) {
    // create a n x n topology
    uint32_t n = 7;
    PointToPointHelper p2p;
    PointToPointGridHelper grid (n, n, p2p);
    NS_LOG_DEBUG ("Topology created");

    //// install Internet stack to the nodes
    //InternetStackHelper internet;
    //grid.InstallStack (internet);

    //// assign IP addresses to the grid
    //Ipv4AddressHelper rowIps ("10.0.0.0", "255.255.255.0");
    //Ipv4AddressHelper colIps ("20.0.0.0", "255.255.255.0");
    //grid.AssignIpv4Addresses (rowIps, colIps);

    // get the center node as the root
    Ptr<Node> root = grid.GetNode ((n-1)/2, (n-1)/2);

    // test root node degree
    NS_TEST_EXPECT_MSG_EQ (root->GetNDevices (), 4, "The root node degree should be 4");

    NS_TEST_ASSERT_MSG_EQ (root->GetId (), 24, "The test case expects node-24 to be the root node");
      
    //construct the test vectors
    uint32_t nbr0Limit[] = {24};
    uint32_t nbr1Limit[] = {23, 17, 25, 31};
    uint32_t nbr2Limit[] = {10, 16, 18, 22, 26, 30, 32, 38};
    uint32_t nbr3Limit[] = {3, 9, 11, 15, 19, 21, 27, 29, 33, 37, 39, 45};
    
    // report test result
    NS_TEST_EXPECT_MSG_EQ (GetNeighborsAtHop (root, 0), nbr0Limit, "0-tier should be the root node itself");
    NS_TEST_EXPECT_MSG_EQ (GetNeighborsAtHop (root, 1), nbr1Limit, "There should be 4 neighbors at the 1st tier or the root node");
    NS_TEST_EXPECT_MSG_EQ (GetNeighborsAtHop (root, 2), nbr2Limit, "There should be 8 neighbors at the 2nd tier or the root node");
    NS_TEST_EXPECT_MSG_EQ (GetNeighborsAtHop (root, 3), nbr3Limit, "There should be 4 neighbors at the 3rd tier or the root node");
    NS_TEST_EXPECT_MSG_EQ (GetNeighborsAtHop (root, 100).GetN (), 0, "The method should return an empty NodeContainer");

    return false;
  }
};

class GetTwoNodesAtRandomTestCase : public TestCase
{
public:
  GetTwoNodesAtRandomTestCase () : TestCase ("Test getting multiple random pair of nodes between which the distance of seperation is specified") {}
  virtual bool DoRun (void) {
    typedef pair<Ptr<Node>, Ptr<Node> > Edge_t;
    for (uint32_t hop=1; hop<=12; hop++) {
      for (uint32_t i=0; i<100;) {
        Edge_t e = GetTwoNodesAtRandom (hop);
        Ptr<Node> local = e.first;
        Ptr<Node> remote = e.second;
        if (!local || !remote)
          // skip as the GetTwoNodesAtRandom() failed to get a nodes pair with such a long distance apart
          continue;
        NodeContainer remoteLimit = GetNeighborsAtHop (local, hop);
        bool remoteIsValid = (find (remoteLimit.Begin (), remoteLimit.End (), remote) != remoteLimit.End ());
        NS_TEST_EXPECT_MSG_EQ (remoteIsValid, true, "The two nodes "
          << local->GetId () << ", " 
          << remote->GetId () << " are infact not seperated by " 
          << hop << " hops apart");
        i++;
      }
    }
    return false;
  }
};


class GetRemoteNodeTestCase : public TestCase
{
public:
  GetRemoteNodeTestCase () : TestCase ("Test reaching the opposite node from one end of an edge") {}

  virtual bool DoRun (void) {
    // create a star topology with n0 as the hub and n1, n2, n3 as leafs
    NetDeviceContainer devs;
    NodeContainer n0n1;
    NodeContainer n0n2;
    NodeContainer n0n3;
    n0n1.Create (2);
    n0n2.Add (n0n1.Get (0));
    n0n2.Create (1);
    n0n3.Add (n0n1.Get (0));
    n0n3.Create (1);
    PointToPointHelper p2p;
    devs.Add (p2p.Install (n0n1));
    devs.Add (p2p.Install (n0n2));
    devs.Add (p2p.Install (n0n3));

    //// install Internet stack to nodes
    //InternetStackHelper internet;
    //internet.Install (n0n1);
    //internet.Install (n0n2.Get (1));
    //internet.Install (n0n3.Get (1));

    //// assign IP addresses to the grid
    //Ipv4AddressHelper ip ("30.0.0.0", "255.255.255.0");
    //ip.Assign (devs);

    // test the number of net devices installed on each node
    Ptr<Node> n0 = n0n1.Get (0);
    Ptr<Node> n1 = n0n1.Get (1);
    Ptr<Node> n2 = n0n2.Get (1);
    Ptr<Node> n3 = n0n3.Get (1);
 
    NS_TEST_EXPECT_MSG_EQ (n0->GetNDevices (), 3, "These should be only 3 net devices on node n0");
    NS_TEST_EXPECT_MSG_EQ (n1->GetNDevices (), 1, "These should be only 1 net devices on node n0");
    NS_TEST_EXPECT_MSG_EQ (n2->GetNDevices (), 1, "These should be only 1 net devices on node n0");
    NS_TEST_EXPECT_MSG_EQ (n3->GetNDevices (), 1, "These should be only 1 net devices on node n0");

    NS_TEST_EXPECT_MSG_EQ (GetRemoteNode (n0, 0)->GetId (), n1->GetId (), "The remote node returned is incorrect");
    NS_TEST_EXPECT_MSG_EQ (GetRemoteNode (n0, 1)->GetId (), n2->GetId (), "The remote node returned is incorrect");
    NS_TEST_EXPECT_MSG_EQ (GetRemoteNode (n0, 2)->GetId (), n3->GetId (), "The remote node returned is incorrect");
    NS_TEST_EXPECT_MSG_EQ (GetRemoteNode (n1, 0)->GetId (), n0->GetId (), "The remote node returned is incorrect");
    NS_TEST_EXPECT_MSG_EQ (GetRemoteNode (n2, 0)->GetId (), n0->GetId (), "The remote node returned is incorrect");
    NS_TEST_EXPECT_MSG_EQ (GetRemoteNode (n3, 0)->GetId (), n0->GetId (), "The remote node returned is incorrect");

    return false;
  }
};

class InstallGridTrafficTestCase : public TestCase
{
public:
  InstallGridTrafficTestCase () : TestCase ("Test installing virtical and horizontal traffic flows to several grid topologies") {}
  virtual bool DoRun (void) {

    Ipv4AddressHelper rowNetworks ("10.0.0.0", "255.255.0.0", Ipv4Address::GetZero ());
    Ipv4AddressHelper colNetworks ("11.0.0.0", "255.255.0.0", Ipv4Address::GetZero ());
    // create a n x n topology
    uint32_t maxN = 20;
    for (uint32_t n=3; n<=maxN; n++) {
      PointToPointHelper p2p;
      p2p.SetDeviceAttribute ("DataRate", DataRateValue (DataRate ("100Mb/s")));
      PointToPointGridHelper grid (n, n, p2p);
      NS_LOG_DEBUG ("Created " << n << "-by-" << n << " grid topology");

      // install internet protocol stack
      InternetStackHelper internet;
      grid.InstallStack (internet);

      // get a new range of IPv4 addresses for assigning the new grid network
      Ipv4AddressHelper rowIps (rowNetworks.NewAddress (), "255.255.255.252");
      Ipv4AddressHelper colIps (colNetworks.NewAddress (), "255.255.255.252");
      rowNetworks.NewNetwork ();
      colNetworks.NewNetwork ();
      // assign IP addresses
      grid.AssignIpv4Addresses (rowIps, colIps);
      NS_LOG_DEBUG ("IPv4 addresses assigned");

      // allocate traffic flows over the grid
      for (uint32_t len=1; len<n; len++) {
        ApplicationContainer apps = InstallGridTraffic (grid, n, n, len, DataRate ("10Mb/s"));
        NS_TEST_EXPECT_MSG_EQ (apps.GetN (), 2*(n-len)*n*2*2, "Number of applications installed should be " << 2*(n-len)*n*2*2);
        NS_LOG_DEBUG ("done n=" << n << ", len=" << len);
      }
    }

    return false;
  }
};

class ComplexBehaviorTestSuite : public TestSuite
{
public:
  ComplexBehaviorTestSuite () 
    : TestSuite ("complex-behavior-tools", UNIT) 
  {
    AddTestCase (new CountNumActivePacketOverTimeTestCase ());
    // A grid topology is created here and the grid is further used in the subsequence test cases
    AddTestCase (new GetTimeIntervalTestCase ());
    AddTestCase (new GetNeighborsAtHopTestCase()); 
    AddTestCase (new GetTwoNodesAtRandomTestCase ());    
    AddTestCase (new InstallGridTrafficTestCase ());
    AddTestCase (new GetRemoteNodeTestCase ());    
  }
} complexBehaviorTestSuite;


} // namespace eecityu
} // namespace ns3